#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int minDistance(string w1, string w2) {
        int n = w1.size();
        int m = w2.size();
        
        // 确保使用较短的字符串长度作为DP数组长度，进一步节省空间
        if (n < m) {
            return minDistance(w2, w1); // 交换后，m变为较短长度
        }
        
        vector<int> dp(m + 1, 0); // 一维DP数组，长度为较短字符串的长度+1
        
        for (int i = 1; i <= n; ++i) {
            int prev = 0; // 保存dp[i-1][j-1]的临时变量
            for (int j = 1; j <= m; ++j) {
                int curr = dp[j]; // 暂存当前dp[j]（即更新前的dp[i-1][j]）
                if (w1[i - 1] == w2[j - 1]) {
                    dp[j] = prev + 1; // 等价于dp[i][j] = dp[i-1][j-1] + 1
                } else {
                    dp[j] = max(dp[j], dp[j - 1]); // 等价于max(dp[i-1][j], dp[i][j-1])
                }
                prev = curr; // 更新prev为下一轮的dp[i-1][j-1]
            }
        }
        
        return n + m - 2 * dp[m];
    }
};

